题目描述

原题

Description:
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:

s = “aa”
p = “a”

Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:

Input:

s = “aa”
p = “a*”

Output: true
Explanation: ‘*’ means zero or more of the precedeng element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

Input:

s = “ab”
p = “.*”

Output: true
Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:

Input:

s = “aab”
p = “cab”

Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches “aab”.

Example 5:

Input:

s = “mississippi”
p = “misis*p.”

Output: false

原题翻译

描述:
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘‘ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
‘‘ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

另外:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

例1:

输入:

s = “aa”
p = “a”

输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

例2:

输入:

s = “aa”
p = “a*”

输出: true
解释: ‘*’ 代表可匹配零个或多个前面的元素, 即可以匹配 ‘a’ 。因此, 重复 ‘a’ 一次, 字符串可变为 “aa”。

例3:

输入:

s = “ab”
p = “.*”

输出: true
解释: “.*” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。

例4:

输入:

s = “aab”
p = “cab”

输出: true
解释: ‘c’ 可以不被重复, ‘a’ 可以被重复一次。因此可以匹配字符串 “aab”。

例5:

输入:

s = “mississippi”
p = “misis*p.”

输出: false

解法一

主要思想

递归地判断当前位置是否匹配。

运行速度：超过了14.44%的解答。

内存使用：超过了35.35%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) //保证p非空
            return s.isEmpty();
        //第0个字符是否匹配
        boolean first_match = (!s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));

        //p下一个字符是不是*
        if (p.length() >= 2 && p.charAt(1) == '*') {       
            /**
             * 如果是，两种情况：
             * 1. 前面第0个字符出现0次，再比较s和p[2~]的
             * 2. p[0]这个字符可能重复了一次或一次以上，比较s[1~]和p
             */
            return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
        } else {
            //如果不是，递归s和p后面的字符
            return first_match && isMatch(s.substring(1), p.substring(1));
        }
    }
}

解法二

主要思想

动态规划：自顶向下。

运行速度：超过了96.25%的解答。

内存使用：超过了100%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    Boolean[][] memo;
    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return dp(0, 0, s, p);
    }

    public boolean dp(int i, int j, String s, String p) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        if (j == p.length()) {
            memo[i][j] = i == s.length();
        } else {
            //s[i]和p[j]是否匹配
            boolean first_match = 
            (i < s.length() &&  (p.charAt(j) == s.charAt(i) ||  p.charAt(j) == '.'));

            if (j + 1 < p.length() && p.charAt(j+1) == '*') {
                memo[i][j] = (dp(i, j+2, s, p) || first_match && dp(i+1, j, s, p));
            } else {
                memo[i][j] = first_match && dp(i+1, j+1, s, p);
            }
        }
        return memo[i][j];
    }
}

解法三

主要思想

动态规划：自下向上。

运行速度：超过了49.75%的解答。

内存使用：超过了100%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;

        for (int i = s.length(); i >= 0; i--){
            for (int j = p.length() - 1; j >= 0; j--){
                //s[i]和p[j]是否匹配
                boolean first_match = 
                    (i < s.length() && (p.charAt(j) == s.charAt(i) ||  p.charAt(j) == '.'));
                if (j + 1 < p.length() && p.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

解法四

主要思想

  1. 如果p.charAt(j) == s.charAt(i)，那么dp[i][j] = dp[i-1][j-1];
  2. 如果p.charAt(j) == ‘.’ ，那么dp[i][j] = dp[i-1][j-1];
  3. 如果p.charAt(j) == ‘*’，

(1) 如果p.charAt(j-1) != s.charAt(i)，那么

1
dp[i][j] = dp[i][j-2] // a*表示空（0个a）

(2) 如果p.charAt(i-1) == s.charAt(i) 或者 p.charAt(i-1) == ‘.’，那么

1
2
3
   dp[i][j] = dp[i-1][j]    // a*表示多个ass
|| dp[i][j] = dp[i][j-1]    // a*表示一个a
|| dp[i][j] = dp[i][j-2]    // a*表示空

运行速度：超过了49.75%的解答。

内存使用：超过了100%的解答。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
             }
        }
        for (int i = 0 ; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.') {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == s.charAt(i)) {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    } else {
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}